package com.shm.leetcode;

import java.util.*;

/**
 * @author: shm
 * @dateTime: 2020/9/21 18:41
 * @description: 140. 单词拆分 II
 * 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
 *
 * 说明：
 *
 * 分隔时可以重复使用字典中的单词。
 * 你可以假设字典中没有重复的单词。
 * 示例 1：
 *
 * 输入:
 * s = "catsanddog"
 * wordDict = ["cat", "cats", "and", "sand", "dog"]
 * 输出:
 * [
 *   "cats and dog",
 *   "cat sand dog"
 * ]
 * 示例 2：
 *
 * 输入:
 * s = "pineapplepenapple"
 * wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
 * 输出:
 * [
 *   "pine apple pen apple",
 *   "pineapple pen apple",
 *   "pine applepen apple"
 * ]
 * 解释: 注意你可以重复使用字典中的单词。
 * 示例 3：
 *
 * 输入:
 * s = "catsandog"
 * wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出:
 * []
 */
public class WordBreakII {
    public List<String> wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        List<String> list = new ArrayList<>();
        StringBuffer sb = new StringBuffer();
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j]&&wordDict.contains(s.substring(j,i))){
                    dp[i] = true;
                    sb.append(s.substring(j,i)).append(" ");
                    continue;
//                    break;
                }
            }
            if (dp[s.length()]){
                list.add(sb.toString());
            }
        }
        return list;

//        return word_Break(s, wordDict, 0);
    }

    /**
     * @author: shm
     * @dateTime: 2020/9/21 19:31
     * @description:
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/word-break-ii/solution/dan-ci-chai-fen-ii-by-leetcode/
     */
    public List<String> word_Break(String s, List<String> wordDict, int start) {
        LinkedList<String> res = new LinkedList<>();
        if (start == s.length()) {
            res.add("");
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end))) {
                List<String> list = word_Break(s, wordDict, end);
                for (String l : list) {
                    res.add(s.substring(start, end) + ("".equals(l) ? "" : " ") + l);
                }
            }
        }
        return res;
    }


    /**
     * @author: shm
     * @dateTime: 2020/9/21 21:52
     * @description: 方法②、dp
     * 实现思路
     * s = "catsandog"
     * wordDict = ["cats", "dog", "sand", "and", "cat"]
     *
     * s 中，catsand 可以分割为 [cats, and] 和 [cat, sand]，因此我们遍历过程中，存储好 [0, i] 位置可以分割成的所有字符串，比如 catsand，它可以分割的字符串集合为 ["cat sand", "cats, and"] ，那么我们后面的字符串 dog 就可以直接跟这两个序列进行拼接, 变成 ["cat sand dog"] 和 ["cats and dog"]
     *
     * 我们同时需要跟 139.单词拆分一样，使用一个 dp 数组记录哪个位置能够进行拆分
     *
     * dp[i] = true; 表示 [0, i] 位置可以分割为 wordDict 中存在的单词
     * 但是遗憾的是，上面的方法仍然是在方法① 中的案例超时：
     *
     * "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
     * ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
     *
     * 这时我看了别人 AC 的方法，基本都是使用 139 的方法提前判断 s 是否能够分割，如果不能，那么直接返回，
     * 上面那个测试属于无法分割的例子，因此直接返回了，而如果把中间的 b 改成 a ，那么那些 AC 的方法也超时了
     * 这大概就是面向测试用例编程，不过没办法，我也只能进行提前判断
     * 作者：suan-tou-wang-ba
     * 链接：https://leetcode-cn.com/problems/word-break-ii/solution/leetcode-140-dan-ci-chai-fen-iiwo-gan-jio-jiang-de/
     */
    public List<String> wordBreak_2(String s, List<String> wordDict) {
        int len = s.length();

        //将字典存放在 set 中，方便 O(1) 查找
        Set<String> set = new HashSet<>(wordDict);

        boolean[] dp = new boolean[len + 1];
        dp[0] = true;


        List<String>[] strs = new List[len + 1];
        for(int i = 0; i <= len; i++){
            strs[i] = new ArrayList<>();
        }
        for(int i = 1; i <= len; i++){
            for(int j = 0; j < i; j++){
                String str = s.substring(j, i);
                if(dp[j] && set.contains(str)){

                    dp[i] = true;

                    //进行字符串拼接，跟上面的 dog 和 前面的拼接例子一样
                    if(j == 0){
                        strs[i].add(str);
                    }else{
                        for(String ss : strs[j]){
                            StringBuilder sb = new StringBuilder(ss).append(" ").append(str);
                            strs[i].add(sb.toString());
                        }
                    }
                }
            }
        }
        return strs[len];
    }

    /**
     * @author: shm
     * @dateTime: 2020/9/22 10:15
     * @description: 方法③、dp 优化
     * 实现思路
     * 使用 O(n) 时间提前预处理 字符串可以分割的位置
     *
     * 如果 最后 dp[len] == false，那么表示原串 s 无法进行分割，提前返回，否则，按照 方法② 进行分割
     *
     * 作者：suan-tou-wang-ba
     * 链接：https://leetcode-cn.com/problems/word-break-ii/solution/leetcode-140-dan-ci-chai-fen-iiwo-gan-jio-jiang-de/
     */
    public List<String> wordBreak_3(String s, List<String> wordDict) {
        int len = s.length();

        Set<String> set = new HashSet<>(wordDict);

        /*
        dp 处理，dp[i] 表示 [0, i] 是否能够 通过分割 或 不分割 使得处理后的字符串存在于字典中
        比如  s = catsand, wordDict = ["cat", "sand"]
        我们可以通过分割成 cat 和 sand 使得分割后的字符串存在于字典中, dp[i] = true;
        比如  s = catsand, wordDict = ["catsand"]
        我们可以不分割就使得原字符串存在于字典中, dp[i] = true;
        比如  s = catsand, wordDict = ["cats"]
        我们无论分割还是不分割都无法使得字符串都存在于字典中, dp[i] = false;
        */
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for(int i = 1; i <= len; i++){
            for(int j = 0; j < i; j++){
                if(dp[j] && set.contains(s.substring(j, i))){
                    dp[i] = true;
                }
            }
        }
        //原字符串 s 无法处理成字典中的字符串
        if(!dp[len]){
            return new ArrayList<>();
        }
        List<String>[] strs = new List[len + 1];
        for(int i = 0; i <= len; i++){
            strs[i] = new ArrayList<>();
        }
        for(int i = 1; i <= len; i++){
            if(!dp[i]){
                continue;
            }
            for(int j = 0; j < i; j++){
                if(!dp[j]){
                    continue;
                }
                String str = s.substring(j, i);
                if(!set.contains(str)){
                    continue;
                }
                if(strs[j].isEmpty()){
                    strs[i].add(str);
                }else{
                    for(String ss : strs[j]){
                        strs[i].add(new StringBuilder(ss).append(" ").append(str).toString());
                    }
                }
            }
        }
        return strs[len];
    }
}
